package com.atguigu.tree;

import com.atguigu.sort.ArrCreator;

import java.util.Arrays;

/**
 * The type Heap sort.
 *
 * 耗时:
 * work: 0.012s
 * 千万: 1.7s
 * 亿级: 6.4s
 *
 */
public class HeapSort {
    /**
     * The entry point of application.
     *
     * @param args the input arguments
     */
    public static void main(String[] args) {
        /**
         *      4
         *  L6          R8
         * L5   R9
         */
//        int[] arr={774, 935, 669, 747, 798, 215, 462, 521, 371, 913};
//        int[] arr={774, 935, 669, 747, 913, 215, 462, 521, 371, 798};
        int[] arr = ArrCreator.createRandArr(ArrCreator.testVelocitySize*1000);
        ArrCreator.beforeSort();
//        System.out.println("init="+Arrays.toString(arr));
//        adjustHeap(arr,0,arr.length);
        sort(arr);
        ArrCreator.afterSort();

//        System.out.println("result="+Arrays.toString(arr));
    }

    /**
     * Sort.
     * 思路:
     * 1. 先构建大顶堆
     * 2. 大顶堆不断从顶部将数据挪至尾部, 并缩减规模
     * 3. 再次构建大顶堆
     *
     * @param arr the arr
     */
    public static void sort(int[] arr){
        // 逆序从最后一个非叶子节点, 构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            adjustHeap(arr,i,arr.length);
//            System.out.println("d:"+i+"-"+Arrays.toString(arr));
        }

//        System.out.println("ddd="+ Arrays.toString(arr));

        // 切换位置
        int temp;
        for(int j=arr.length-1;j>0;j--){
            temp=arr[j];
            arr[j]=arr[0];
            arr[0]=temp;

            // 为什么这里只执行一次[自顶而下构建]就可以构建出完好的大顶堆? 而不像开头需要再次逆序遍历才能构建.
            /*
             * 解析: 大顶堆的一个特点, 是父节点必定大于两个子节点, 因此也必然大于所有后代节点. (但并不意味着所有后一层级的节点都小于等于前一层级)
             * 在进行完一次置换后, 首节点必定不符合规范, 因此与次一层进行对比更换, 逐次向下.
             * 而其他未更换过的(局部顶点)节点, 其与下部构建而成的大顶堆, 则不需要变动.
             */
            adjustHeap(arr,0,j);

        }

    }

    /**
     * 构建大顶堆
     * 自上而下的构建一次
     * (如果是完全乱序, 一次调用并不能保证构建出大顶堆, 只有逆序连续遍历调用才能保证构建出来)
     * (但如果只是将原本是大顶堆的头部和尾部切换一次, 则可保证一次再构建大顶堆, 原因见sort方法)
     *
     * 执行此方法的时间复杂度是O(logn)
     *
     * @param arr    the arr 原始数组
     * @param i      the 二叉树定点下标
     * @param length the length 构建大顶堆的限制长度
     */
    public static void adjustHeap(int[] arr,int i,int length){
        // 记录当前树的顶点数,称为方法顶点数
        int temp=arr[i];
        for(int k=i*2+1;k<length;k=k*2+1){
            // 先比较左右两节点,找到较大节点
            if(k+1<length&&arr[k+1]>arr[k]){
                k++;
            }
            if(temp<arr[k]){
                // 如果顶点比左右某个节点小, 则将当前顶点数转为较高值, 再下次遍历时对比方法顶点数与下个子树的左右节点
                arr[i]=arr[k];
                i=k;
            }else{
                // 如果方法顶点数已经大于左右的两个节点, 则可结束. 因为此处已经假定了, 后续的子树都是大顶堆
                break;
            }
        }
        // 将当前排到的(可能是某个子树)顶点,赋值给方法顶点数
        arr[i]=temp;
    }
}
